package com.shm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * 5508. 数的平方等于两数乘积的方法数
 * 题目难度 Medium
 * 给你两个整数数组 nums1 和 nums2 ，请你返回根据以下规则形成的三元组的数目（类型 1 和类型 2 ）：
 *
 * 类型 1：三元组 (i, j, k) ，如果 nums1[i]2 == nums2[j] * nums2[k] 其中 0 <= i < nums1.length 且 0 <= j < k < nums2.length
 * 类型 2：三元组 (i, j, k) ，如果 nums2[i]2 == nums1[j] * nums1[k] 其中 0 <= i < nums2.length 且 0 <= j < k < nums1.length
 *
 *
 * 示例 1：
 *
 * 输入：nums1 = [7,4], nums2 = [5,2,8,9]
 * 输出：1
 * 解释：类型 1：(1,1,2), nums1[1]^2 = nums2[1] * nums2[2] (4^2 = 2 * 8)
 * 示例 2：
 *
 * 输入：nums1 = [1,1], nums2 = [1,1,1]
 * 输出：9
 * 解释：所有三元组都符合题目要求，因为 1^2 = 1 * 1
 * 类型 1：(0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2), nums1[i]^2 = nums2[j] * nums2[k]
 * 类型 2：(0,0,1), (1,0,1), (2,0,1), nums2[i]^2 = nums1[j] * nums1[k]
 * 示例 3：
 *
 * 输入：nums1 = [7,7,8,3], nums2 = [1,2,9,7]
 * 输出：2
 * 解释：有两个符合题目要求的三元组
 * 类型 1：(3,0,2), nums1[3]^2 = nums2[0] * nums2[2]
 * 类型 2：(3,0,1), nums2[3]^2 = nums1[0] * nums1[1]
 * 示例 4：
 *
 * 输入：nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]
 * 输出：0
 * 解释：不存在符合题目要求的三元组
 *
 *
 * 提示：
 *
 * 1 <= nums1.length, nums2.length <= 1000
 * 1 <= nums1[i], nums2[i] <= 10^5
 * @author SHM
 */
public class NumTriplets {
    //超时
    public int numTriplets(int[] nums1, int[] nums2) {
//        [43024,99908]
//        [1864]
//        int[] ints1 = {43024, 99908};
//        int[] ints2 = {1864};
//        if (nums1 == ints1 && nums2 == ints2){
//            return 0;
//        }

        int cnt = 0;
        ArrayList<Long> list1 = new ArrayList<>();
        for (int j = 0; j < nums2.length-1; j++) {
            for (int k=j+1;k<nums2.length;k++){
                list1.add((long)nums2[j]*(long)nums2[k]);
            }
        }
        for (int value : nums1) {
            long key = (long)value * (long)value;
            for (Long aLong : list1) {
                if (key == aLong) {
                    cnt++;
                }
            }
        }

        ArrayList<Long> list2 = new ArrayList<>();
        for (int j = 0; j < nums1.length-1; j++) {
            for (int k=j+1;k<nums1.length;k++){
                list2.add((long)nums1[j]*(long)nums1[k]);
            }
        }
        for (int j : nums2) {
            long key = (long)j * (long)j;
            for (Long aLong : list2) {
                if (key == aLong) {
                    cnt++;
                }
            }
        }
        return cnt;
    }

    //超时
    public int numTriplets_2(int[] nums1, int[] nums2) {
        int cnt = 0;
        for (int i = 0; i < nums1.length; i++) {
            long key  = (long)nums1[i] * (long)nums1[i];
            for (int j = 0; j < nums2.length-1; j++) {
                for (int k=j+1;k<nums2.length;k++){
                    long temp = (long)nums2[j]*(long)nums2[k];
                    if (key==temp){
                        cnt++;
                    }
                }
            }
        }
        for (int i = 0; i < nums2.length; i++) {
            long key = (long)nums2[i]*(long)nums2[i];
            for (int j = 0; j < nums1.length-1; j++) {
                for (int k=j+1;k<nums1.length;k++){
                    long temp = (long)nums1[j]*(long)nums1[k];
                    if (key==temp){
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }

    /**
     * 这个题目有两个坑：
     * 1、乘积可能超过int最大值。
     * 2、注意时间复杂度，使用map防止超时。
     * @param nums1
     * @param nums2
     * @return
     */
    public int numTriplets_3(int[] nums1, int[] nums2) {
        return cal(nums1,nums2)+cal(nums2,nums1);
    }

    public int cal(int[] num1,int[] num2){
        int cnt = 0;
        Map<Long,Integer> map = new HashMap<>();
        for (int j = 0; j < num2.length-1; j++) {
            for (int k=j+1;k<num2.length;k++){
                long l = (long) num2[j] * (long) num2[k];
                if (map.containsKey(l)){
                    map.put(l,map.get(l)+1);
                }else {
                    map.put(l, 1);
                }
            }
        }

        for (int i : num1) {
            long l = (long) i * (long) i;
            if (map.containsKey(l)){
                cnt+=map.get(l);
            }
        }

        return cnt;
    }

}
